package lc.q51_100;

import java.util.HashMap;
import java.util.Iterator;
import java.util.Map;

public class Q76 {

    public static void main(String[] args) {
        Q76 q76 = new Q76();
        System.out.println(q76.minWindow("ADOBECODEBANC", "ABC"));
    }

    public String minWindow(String s, String t) {
        Map<Character, Integer> tMap = new HashMap<>();
        Map<Character, Integer> sMap = new HashMap<>();
        for (char c : t.toCharArray()) {
            tMap.put(c, tMap.getOrDefault(c, 0) + 1);
        }
        // 循环s，并检测sMap跟tMap的值
        int end = -1;
        int start = 0;
        int sLen = s.length();
        int ansL = -1;
        int andR = -1;
        int len = Integer.MAX_VALUE;
        while (end < sLen) {
            end ++;
            if (end < sLen && tMap.containsKey(s.charAt(end))) {
                char c = s.charAt(end);
                sMap.put(c, sMap.getOrDefault(c, 0) + 1);
            }
            while (check(sMap, tMap) && start <= end) {
                if (end - start + 1 < len) {
                    // 更新最新的值
                    len = end - start + 1;
                    ansL = start;
                    andR = start + len;
                }
                if (tMap.containsKey(s.charAt(start))) {
                    char c2 = s.charAt(start);
                    sMap.put(c2, sMap.getOrDefault(c2, 0) - 1);
                }
                start ++;
            }
        }
        return ansL == -1 ? "": s.substring(ansL, andR);
    }

    private boolean check(Map<Character, Integer> sMap, Map<Character, Integer> tMap) {
        for (Map.Entry<Character, Integer> entry : tMap.entrySet()) {
            Character key = entry.getKey();
            Integer value = entry.getValue();
            // sMap中的值必须不比value小
            Integer sValue = sMap.getOrDefault(key, 0);
            if (sValue < value) {
                return false;
            }
        }
        return true;
    }

}
